package org.xi.dsaa.collection;

/**
 * 二叉搜索树
 *
 * @param <E> 元素类型
 */
public class BinarySearchTree<E extends Comparable<E>> {

    private Node<E> root;

    public boolean exists(E item) {
        return getNode(item) != null;
    }

    public void addAll(E... items) {
        for (E item : items) {
            add(item);
        }
    }

    public void addAll(Iterable<E> items) {
        for (E item : items) {
            add(item);
        }
    }

    public void add(E item) {
        if (root == null) {
            root = new Node<>(item);
            return;
        }
        Node<E> node = root, tmpNode = root;
        while (tmpNode != null) {
            int compareResult = node.item.compareTo(item);
            if (compareResult > 0) {
                tmpNode = node.left;
                if (node.left == null) {
                    node.left = new Node<>(item);
                }
            } else if (compareResult < 0) {
                tmpNode = node.right;
                if (node.right == null) {
                    node.right = new Node<>(item);
                }
            } else {
                return;
            }
            node = tmpNode;
        }
    }

    private Node<E> getNode(E item) {
        int compareResult;
        for (Node<E> node = root; node != null; node = compareResult > 0 ? node.left : node.right) {
            if ((compareResult = node.item.compareTo(item)) == 0) {
                return node;
            }
        }
        return null;
    }

    public void remove(E item) {
        root = remove(item, root);
    }

    public Node<E> remove(E item, Node<E> node) {
        if (node == null) {
            return null;
        }
        int compareResult = item.compareTo(node.item);
        if (compareResult > 0) {
            node.right = remove(item, node.right);
        } else if (compareResult < 0) {
            node.left = remove(item, node.left);
        } else if (node.left != null && node.right != null) {

            // 替换左子树最大值或者右子树最小值都可以

            // 获取左子树最大值
            Node<E> maxNode = getMaxNode(node.left);
            // 替换当前node值为新值
            node.item = maxNode.item;
            // 删左子树之前的最大值
            node.left = remove(maxNode.item, node.left);

            // // 获取右子树最小值
            // Node<E> minNode = getMinNode(node.right);
            // // 替换当前node值为新值
            // node.item = minNode.item;
            // // 删右子树之前的最小值
            // node.right = remove(minNode.item, node.right);
        } else {
            return node.left != null
                    ? node.left
                    : node.right;
        }
        return node;
    }

    public E getMin() {
        Node<E> node = getMinNode(root);
        return node == null ? null : node.item;
    }

    public E getMax() {
        Node<E> node = getMaxNode(root);
        return node == null ? null : node.item;
    }

    private boolean isRoot(final Node<E> node) {
        return node == root;
    }

    private boolean isLeaf(final Node<E> node) {
        return node.left == null && node.right == null;
    }

    private Node<E> getMinNode(final Node<E> node) {
        Node<E> currentNode = node;
        if (currentNode == null) {
            return null;
        }
        while (currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode;
    }

    private Node<E> getMaxNode(final Node<E> node) {
        Node<E> currentNode = node;
        if (currentNode == null) {
            return null;
        }
        while (currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode;
    }

    public void printTree() {
        printTree(root);
    }

    private void printTree(Node<E> node) {
        if (node.left != null) {
            printTree(node.left);
        }
        if (node.right != null) {
            printTree(node.right);
        }
        System.out.print(node.item + ", ");
    }

    public static class Node<E extends Comparable<E>> {
        private E item;
        private Node<E> left;
        private Node<E> right;

        public Node(E item) {
            this(item, null, null);
        }

        public Node(E item, Node<E> left, Node<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        tree.addAll(4,2,1,3,6,5,7);
        tree.printTree();

//        System.out.println();
//        System.out.println();
//        tree.remove(6);
//        tree.printTree();
//
//        System.out.println();
//        System.out.println();
//        tree.remove(9);
//        tree.printTree();
    }
}
